package datastructure.sort;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/25 9:10 下午
 */
public class HeapSort  {
    /**
     * 小顶堆 从大到小排序
     * @param arr
     * @param <T>
     */
    public static <T extends Comparable<? super T>>void heapSort(T[] arr){
        for (int i = arr.length/2; i >=0 ; i--) {
            perDown(arr,i,arr.length);
        }
        for (int i=arr.length-1;i>=0;i--){
            swap(arr,0,i);
            perDown(arr,0,i);
        }
    }

    private static<T extends Comparable<? super T>> void perDown(T[] arr, int i, int length) {
        T temp;
        int child;
        for (temp=arr[i];leftChild(i)<length;i=child){
            child=leftChild(i);
            if (child!=length-1 && arr[child].compareTo(arr[child+1])>0){
                child++;
            }
            if (arr[child].compareTo(temp)<0){
                arr[i]=arr[child];
            }else {
                break;
            }
        }
        arr[i]=temp;
    }

    private static<T extends Comparable<? super T>> void swap(T[] arr, int p, int q) {
        T temp=arr[p];
        arr[p]=arr[q];
        arr[q]=temp;
    }



    private static int leftChild(int i) {
        return i*2+1;
    }

    /**
     * 大顶堆 从小到大排序
     * @param arr
     * @param <T>
     */
    public static <T extends Comparable<? super T>>void maxheapSort(T[]arr){
        for (int i = arr.length/2; i >=0 ; i--) {
            perUp2(arr,i,arr.length);
        }
        for (int i = arr.length-1; i >=0 ; i--) {
            swap(arr,0,i);
            perUp2(arr,0,i);
        }
    }

    private static<T extends Comparable<? super T>> void perUp(T[] arr, int i, int length) {
        T temp;
        int child;
        for (temp=arr[i];leftChild(i)<length;i=child){
            child=leftChild(i);
            if (child!=length-1 && arr[child].compareTo(arr[child+1])<0){
                child++;
            }
            if (arr[child].compareTo(temp)>0){
                arr[i]=arr[child];
            }
        }
        arr[i]=temp;
    }

    private static <T extends Comparable<? super T>> void perUp2(T[]arr,int i,int length){
        T temp;
        int child;
        for (temp=arr[i];leftChild(i)<length;i=child){
            child=leftChild(i);

            if (child!=length-1 && arr[child].compareTo(arr[child+1])<0){
                child++;
            }
            if (arr[child].compareTo(temp)>0){
                arr[i]=arr[child];
            }else {
                break;
            }
        }
        arr[i]=temp;
    }

    public static void main(String[] args) {
        Integer[] array =new Integer[10];
        for (int i=0;i<10;i++){
            array[i]=(int)(Math.random()*1000);
        }
        Integer[] integers = {1,2,3,4,4552422,123445,3467,74};
        heapSort(integers);
        for (int i:integers){
            System.out.println(i);
        }
    }
}
